<!doctype html><html lang=cn-zh><head><meta charset=UTF-8><meta name=viewport content="width=device-width,initial-scale=1"><meta http-equiv=X-UA-Compatible content="IE=edge"><style type=text/css>body{font-family:monospace}</style><title>《算法图解》读书笔记3-递归</title>
<meta name=description content="A blog maintained by Vimiix."><link rel=stylesheet href=/css/style.css><script>var _hmt=_hmt||[];(function(){var e,t=document.createElement("script");t.src="https://hm.baidu.com/hm.js?7c24231917964240bae97e813810620c",e=document.getElementsByTagName("script")[0],e.parentNode.insertBefore(t,e)})()</script></head><body><header>====================<br>== Hi, I'm Vimiix ==<br>====================<div style=float:right;color:gray;font-size:x-large>Get hands dirty.</div><br><p><nav><a href=https://www.vimiix.com/><b>首页</b></a>.
<a href=/posts/><b>文章列表</b></a>.
<a href=/projects/><b>开源项目</b></a>.
<a href=/tags/><b>标签</b></a>.
<a href=/friends/><b>友链</b></a>.
<a href=/about/><b>关于我</b></a>.
<a href=/index.xml><b>RSS</b></a>.</nav></p></header><main><article><h1>《算法图解》读书笔记3-递归</h1><b><time>2018.05.25 19:20</time></b>
<a href=/tags/algorithms>algorithms</a>
<a href=/tags/linux>Linux</a><div><blockquote><p>如果使用循环 ，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。</p></blockquote><h2 id=递归函数>递归函数</h2><p>在一个函数中，可以调用另一个函数，如果调用的另一个函数是函数本身，这样的函数就是递归函数。如下示例：</p><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-python data-lang=python><span style=display:flex><span><span style=color:#66d9ef>def</span> <span style=color:#a6e22e>foo</span>(x):
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>if</span> x <span style=color:#f92672>==</span> <span style=color:#ae81ff>0</span>:
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>return</span> <span style=color:#e6db74>&#39;end&#39;</span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>else</span>:
</span></span><span style=display:flex><span>        <span style=color:#75715e># 在函数中继续调用自己</span>
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>return</span> foo(x<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>)
</span></span></code></pre></div><p>递归函数中，必须有两个条件，来保证函数的能够有效运行并返回。</p><ul><li>基线条件(base case)：即函数停止调用自己的条件，避免无限循环调用产生<a href=https://zh.wikipedia.org/wiki/%E5%A0%86%E7%96%8A%E6%BA%A2%E4%BD%8D>栈溢出</a>，导致程序崩溃；</li><li>递归条件(reversive case)：即函数调用自己的条件，由此形成递归；</li></ul><p>还以上面的代码实例说明：<code>x == 0</code>就是该递归函数的基线条件，<code>else</code> 分支即为递归条件</p><h2 id=栈>栈</h2><p><strong>栈</strong>是一种数据结构，它的结构类似一个桶，只有一个开口处可以进出元素。每次从桶的开口处，放入一个元素，这种操作叫做**“压栈”<strong>（push），一层一层的摞起来，每次读取或删除的时候，只能从最顶部开始一个一个取出，这个操作叫做</strong>“出栈”<strong>（pop）。桶的底部称为</strong>“栈底”<strong>（bottom），桶内最高处的元素（也就是最后放进去的元素）所在的内存地址称为</strong>栈顶**（top）,通过下面一个小动图展示栈的工作原理：</p><p><figure><img src=http://vimiix-blog.oss-cn-qingdao.aliyuncs.com/stack.gif alt></figure></p><p>使用 python 内建数据类型<code>list</code>实现栈的数据结构：</p><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-python data-lang=python><span style=display:flex><span><span style=color:#66d9ef>class</span> <span style=color:#a6e22e>Stack</span>:
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>def</span> __init__(self):
</span></span><span style=display:flex><span>        <span style=color:#75715e># 造一个桶</span>
</span></span><span style=display:flex><span>        self<span style=color:#f92672>.</span>items <span style=color:#f92672>=</span> []
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    <span style=color:#75715e># 压栈</span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>def</span> <span style=color:#a6e22e>push</span>(self, item):
</span></span><span style=display:flex><span>        self<span style=color:#f92672>.</span>items<span style=color:#f92672>.</span>append(item)
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    <span style=color:#75715e># 出栈</span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>def</span> <span style=color:#a6e22e>pop</span>(self):
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>return</span> self<span style=color:#f92672>.</span>items<span style=color:#f92672>.</span>pop()
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    <span style=color:#75715e># 清空栈</span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>def</span> <span style=color:#a6e22e>clear</span>(self):
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>del</span> self<span style=color:#f92672>.</span>items[:]
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    <span style=color:#75715e># 当前栈的大小(元素个数)</span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>def</span> <span style=color:#a6e22e>size</span>(self):
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>return</span> len(self<span style=color:#f92672>.</span>items)
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    <span style=color:#75715e># 栈是否为空</span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>def</span> <span style=color:#a6e22e>empty</span>(self):
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>return</span> self<span style=color:#f92672>.</span>size() <span style=color:#f92672>==</span> <span style=color:#ae81ff>0</span>
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    <span style=color:#75715e># 栈顶元素</span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>def</span> <span style=color:#a6e22e>top</span>(self):
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>return</span> self<span style=color:#f92672>.</span>items[self<span style=color:#f92672>.</span>size()<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>]
</span></span></code></pre></div><h2 id=调用栈>调用栈</h2><p>（引自<a href=https://zh.wikipedia.org/wiki/%E5%91%BC%E5%8F%AB%E5%A0%86%E7%96%8A>维基百科</a>）</p><p>计算机中使用调用栈来存放子程序的返回地址，即当子程序运行结束后应该返回的地址。如果被调用的子程序还要调用其他的子程序，其自身的返回地址就继续压栈到调用栈，在其自身运行完毕后再自行取回。在递归程序中，每一层次递归都必须在调用栈上压栈一条地址，因此如果程序出现无限递归（或仅仅是过多的递归层次），调用栈就会产生栈溢出。（优化方式：<strong>尾递归</strong>优化，实现递归空间复杂度 O(1)）</p><p><strong>调用栈的功能</strong>:</p><p>调用栈的主要功能是存放<a href="https://zh.wikipedia.org/w/index.php?title=%E8%BF%94%E5%9B%9E%E4%BD%8D%E5%9D%80&amp;action=edit&amp;redlink=1">返回地址</a>。除此之外，调用栈还用于存放：</p><ul><li><a href=https://zh.wikipedia.org/wiki/%E6%9C%AC%E5%9C%B0%E8%AE%8A%E6%95%B8>本地变量</a>：子程序的变量可以存入调用栈，这样可以达到不同子程序间变量分离开的作用。</li><li><a href=https://zh.wikipedia.org/wiki/%E5%8F%82%E6%95%B0>参数</a>传递：如果<a href=https://zh.wikipedia.org/wiki/%E6%9A%AB%E5%AD%98%E5%99%A8>寄存器</a>不足以容纳子程序的参数，可以在调用栈上存入参数。</li><li>环境传递：有些语言（如<a href=https://zh.wikipedia.org/wiki/Pascal>Pascal</a>与<a href=https://zh.wikipedia.org/wiki/Ada>Ada</a>）支持“多层子程序”，即子程序中可以利用主程序的本地变量。这些变量可以通过调用栈传入子程序。</li></ul><h2 id=递归应用举例汉诺塔游戏>递归应用举例：汉诺塔游戏</h2><p>学习递归，最经典的一个例子就是通过使用递归实现汉诺塔的解决方案。通俗的代码逻辑，把中间过程的一切逻辑过程都交给计算机去处理。</p><p><strong>游戏规则</strong>：</p><p>有三根杆子 A，B，C。A 杆上有 N 个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：</p><p><figure><img src=http://vimiix-blog.oss-cn-qingdao.aliyuncs.com/hanoi.jpg alt></figure></p><ol><li>每次只能移动一个圆盘；</li><li>大盘不能叠在小盘上面。</li></ol><p>提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。</p><p>问：如何移？最少要移动多少次？</p><p>借助递归，可以清晰简洁的实现解法：</p><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-python data-lang=python><span style=display:flex><span><span style=color:#66d9ef>def</span> <span style=color:#a6e22e>move</span>(n, A, B, C):
</span></span><span style=display:flex><span>    <span style=color:#75715e># 基线条件</span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>if</span> n <span style=color:#f92672>==</span> <span style=color:#ae81ff>1</span>:
</span></span><span style=display:flex><span>        print(A, <span style=color:#e6db74>&#34;-&gt;&#34;</span>, C)
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>return</span>
</span></span><span style=display:flex><span>    <span style=color:#75715e># 将最底下一层上面的所有视为一个整体，借助C移动到B</span>
</span></span><span style=display:flex><span>    move(n<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>, A, C, B)
</span></span><span style=display:flex><span>    <span style=color:#75715e># 将最底下的一层，借助B移动到C</span>
</span></span><span style=display:flex><span>    move(<span style=color:#ae81ff>1</span>, A, B, C)
</span></span><span style=display:flex><span>    <span style=color:#75715e># 将B上剩下的所有层，借助A移动到C</span>
</span></span><span style=display:flex><span>    move(n<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>, B, A, C)
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span><span style=color:#75715e># 测试三层移动结果</span>
</span></span><span style=display:flex><span><span style=color:#f92672>&gt;&gt;&gt;</span> move(<span style=color:#ae81ff>3</span>, <span style=color:#e6db74>&#39;A&#39;</span>, <span style=color:#e6db74>&#39;B&#39;</span>, <span style=color:#e6db74>&#39;C&#39;</span>)
</span></span><span style=display:flex><span>A <span style=color:#f92672>-&gt;</span> C
</span></span><span style=display:flex><span>A <span style=color:#f92672>-&gt;</span> B
</span></span><span style=display:flex><span>C <span style=color:#f92672>-&gt;</span> B
</span></span><span style=display:flex><span>A <span style=color:#f92672>-&gt;</span> C
</span></span><span style=display:flex><span>B <span style=color:#f92672>-&gt;</span> A
</span></span><span style=display:flex><span>B <span style=color:#f92672>-&gt;</span> C
</span></span><span style=display:flex><span>A <span style=color:#f92672>-&gt;</span> C
</span></span><span style=display:flex><span><span style=color:#f92672>&gt;&gt;&gt;</span>
</span></span></code></pre></div><p>— EOF —</p></div></article></main><aside><div><div><h3>LATEST POSTS</h3></div><div><ul><li><a href=/posts/2025-10-16-kubernetes-apiserver-authorization-mechanism/>Kubernetes APIServer 鉴权机制</a></li><li><a href=/posts/2025-09-30-kubernetes-apiserver-authentication-mechanism/>Kubernetes APIServer 认证机制</a></li><li><a href=/posts/2024-12-16-deploy-kubernetes-by-kubeadm/>使用 kubeadm 搭建 kubernetes 集群</a></li><li><a href=/posts/2024-09-20-how-to-code-review/>如何做code review</a></li><li><a href=/posts/2024-08-12-weakref-in-python/>Python中的弱引用</a></li></ul></div></div></aside><footer><p>Social Links:
<a href=https://github.com/vimiix><b>Github</b></a>.
<a href=https://www.douban.com/people/vimiix/><b>Douban</b></a>.
<a href=mailto:i@vimiix.com><b>Email</b></a>.<br><hr>&copy; 2017-2025
Vimiix Yao; All rights reserved.
<a href=https://beian.miit.gov.cn/>京ICP备19015214号-1</a></p><script src=https://l2dwidget.js.org/lib/L2Dwidget.min.js></script><script>L2Dwidget.init({model:{jsonPath:"https://unpkg.com/live2d-widget-model-tororo@1.0.5/assets/tororo.model.json"}})</script></footer></body></html>